package 力扣.堆.滑动窗口.滑动窗口中位数480;

import java.util.Arrays;

public class 滑动窗口中位数480 {
    public static void main(String[] args) {
        int[] ints = {1, 3, -1, -3, 5, 3, 6, 7};
//        int[] ints = {1};
//        int[] ints = {1,4,2,3};
        double[] doubles = medianSlidingWindow(ints, 3);
        System.out.println(Arrays.toString(doubles));
    }
    //疑问1：到k之前如何选择中位数？
    //      排序：奇偶数--》得到中位数
    //疑问2：能否使用数组下标解决？
    //     索引——》出去和进去

    /**
     * 超时版：从nums中截取出长度为k的数组，然后排序，最后根据k从找到数组中的中位数作为结果的一个元素
     * 时间复杂度：O( (num.len - k)klogk )
     * @param nums
     * @param k
     * @return
     */
    public static double[] medianSlidingWindow(int[] nums, int k) {
        if (k == 0){
            double[] res = new double[nums.length - k];
            res[0] = nums[0];
            return res;
        }
        double[] res = new double[nums.length - k + 1];
        int i = 0;
        while ( (nums.length - k) >= i){
            int[] ints = Arrays.copyOfRange(nums, i, i+k);
            Arrays.sort(ints);
            if (k % 2 != 0){
                res[i] = (double) ints[(k+1)/2 - 1];
            }else {
                res[i] = ((double)ints[k/2-1] + (double) ints[k/2])/2;
            }
            i++;
        }
        return res;
    }


}
